﻿namespace ZuoAlgorithms.Class005;

public class Validator
{
    public static void MainValidator()
    {
        // 随机数字最大的长度
        int N = 200;
        // 随机数组每个值，在1~V之间等概率随机
        int V = 1000;
        // testTimes : 测试次数
        int testTimes = 50000;

        Console.WriteLine("测试开始");
        for (int i = 0; i < testTimes; i++)
        {
            // 随机得到一个长度，长度在[0~N-1]
            Random rand = new Random();
            int n = (int)(rand.Next() * N);
            // 得到随机数字
            int[] arr = RandomArray(n, V);
            int[] arr1 = CopayArray(arr);
            int[] arr2 = CopayArray(arr);
            int[] arr3 = CopayArray(arr);
            SelectSort(arr1);
            BubbleSort(arr2);
            InsertionSort(arr3);
            if (!SameArray(arr1, arr2) || !SameArray(arr1, arr3))
            {
                Console.WriteLine("出错了");
            }
        }
        Console.WriteLine("测试结束");
    }


    // 得到一个随机数组，长度是n
    // 数组中每个数，都在1~v之间，随机得到
    public static int[] RandomArray(int n, int v)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            Random rand = new Random();
            arr[i] = (int)(rand.Next() * v) + 1;
        }
        return arr;
    }

    public static int[] CopayArray(int[] arr)
    {
        int n = arr.Length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++)
        {
            res[i] = arr[i];
        }
        return res;
    }

    public static bool SameArray(int[] arr1, int[] arr2)
    {
        int n = arr1.Length;
        for (int i = 0; i < n; i++)
        {
            if (arr1[i] != arr2[i])
            {
                return false;
            }
        }
        return true;
    }

    // 数组中交换i和j位置的数
    public static void Swap(int[] arr, int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    #region 选择排序

    /// <summary>
    /// 选择排序
    /// </summary>
    /// <param name="arr"></param>
    public static void SelectSort(int[] arr)
    {
        if (arr == null || arr.Length < 2)
            return;
        for (int minIndex, i = 0; i < arr.Length - 1; i++)
        {
            minIndex = i;
            for (int j = i + 1; j < arr.Length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            Swap(arr, i, minIndex);
        }
    }

    #endregion

    #region 冒泡排序

    public static void BubbleSort(int[] arr)
    {
        if (arr == null || arr.Length < 2)
            return;
        for (int end = arr.Length - 1; end > 0; end--)
        {
            for (int i = 0; i < end; i++)
            {
                if (arr[i] > arr[i + 1])
                {
                    Swap(arr, i, i + 1);
                }
            }
        }
    }

    #endregion

    #region 插入排序

    public static void InsertionSort(int[] arr)
    {
        if (arr == null || arr.Length < 2)
            return;
        for (int i = 1; i < arr.Length; i++)
        {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
            {
                Swap(arr, j, j + 1);
            }
        }
    }

    #endregion
}
